package com.csdemos.algs;

import static com.csdemos.algs.ArrayUtils.swap;
import static com.csdemos.algs.SortUtils.parent;
import static com.csdemos.algs.SortUtils.maxHeapify;
import static com.csdemos.algs.SortUtils.left;
import static com.csdemos.algs.SortUtils.right;

import java.util.Arrays;

public class PriorityQueue {
	
	private int[] A;
	private int heapSize;
	
	public PriorityQueue() {
		A = new int[0];
		heapSize = 0;
	}
	
	public int buildMinHeap(int[] B) {
		A = Arrays.copyOf(B, B.length);
		heapSize = A.length;
		for (int i = (A.length - 1) / 2; i >= 0; --i) {
			minHeapify(A, i, heapSize);
		}
		return heapSize;
	}
	
	private void minHeapify(int[] A, int i, int heapSize) {
		int l = left(i);
		int r = right(i);
		int smallest;
		if (l < heapSize && A[l] < A[i]) {
			smallest = l;
		} else {
			smallest = i;
		}
		if (r < heapSize && A[r] < A[smallest]) {
			smallest = r;
		}
		if (smallest != i) {
			swap(A, i, smallest);
			minHeapify(A, smallest, heapSize);
		}
	}
	
	public int heapMaximum() {
		return A[0];
	}

	public int heapExtractMax() {
		if (heapSize < 1) {
			throw new IllegalArgumentException("The queue is empty");
		}
		int max = A[0];
		A[0] = A[heapSize - 1];
		heapSize--;
		maxHeapify(A, 0, heapSize);
		return max;
	}
	
	public int heapExtractMin() {
		if (heapSize < 1) {
			throw new IllegalArgumentException("The queue is empty");
		}
		int min = A[0];
		A[0] = A[heapSize - 1];
		heapSize--;
		minHeapify(A, 0, heapSize);
		return min;
	}
	
	public void heapIncreaseKey(int i, int key) {
		if (key < A[i]) {
			throw new IllegalArgumentException("New key is less than current");
		}
		A[i] = key;
		while (i > 0 && A[parent(i)] < A[i]) {
			swap(A, i, parent(i));
			i = parent(i);
		}
	}
	
	public void maxHeapInsert(int key) {
		heapSize++;
		if (heapSize > A.length) {
			int[] B = new int[heapSize];
			for (int i = 0; i < heapSize - 1; ++i) {
				B[i] = A[i];
			}
			A = B;
		}
		heapIncreaseKey(heapSize - 1, key);
	}
	
	public boolean isEmpty() {
		return heapSize == 0;
	}
	
	public boolean contains(int v) {
		for (int i = 0; i < heapSize; i++) {
			if (A[i] == v) {
				return true;
			}
		}
		return false;
	}
	@Override
	public String toString() {
		StringBuilder result = new StringBuilder("[");
		for (int i = 0; i < A.length; ++i) {
			if (i == heapSize) {
				result.append(" | ");
			}
			result.append(A[i]).append(" ");
		}
		return result.append("]").toString();
	}
}
